0095. 不同的二叉搜索树 II【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 递归构建

1. 📝 题目描述

• leetcode

给你一个整数 n，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树。可以按 任意顺序 返回答案。

---

示例 1：

输入：n = 3
输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

示例 2：

输入：n = 1
输出：[[1]]

---

提示：

• 1 <= n <= 8

2. 🎯 s.1 - 递归构建

c

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
struct TreeNode** build(int lo, int hi, int* returnSize) {
    if (lo > hi) {
        *returnSize = 1;
        struct TreeNode** res = (struct TreeNode**)malloc(sizeof(struct TreeNode*));
        res[0] = NULL;
        return res;
    }
    struct TreeNode** result = NULL;
    *returnSize = 0;

    for (int i = lo; i <= hi; i++) {
        int leftSize, rightSize;
        struct TreeNode** lefts = build(lo, i - 1, &leftSize);
        struct TreeNode** rights = build(i + 1, hi, &rightSize);

        result = (struct TreeNode**)realloc(result, sizeof(struct TreeNode*) * (*returnSize + leftSize * rightSize));
        for (int l = 0; l < leftSize; l++) {
            for (int r = 0; r < rightSize; r++) {
                struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
                root->val = i;
                root->left = lefts[l];
                root->right = rights[r];
                result[(*returnSize)++] = root;
            }
        }
        free(lefts);
        free(rights);
    }
    return result;
}

struct TreeNode** generateTrees(int n, int* returnSize) {
    return build(1, n, returnSize);
}

js

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number} n
 * @return {TreeNode[]}
 */
var generateTrees = function (n) {
  const build = (lo, hi) => {
    if (lo > hi) return [null]
    const result = []
    for (let i = lo; i <= hi; i++) {
      for (const left of build(lo, i - 1)) // 枚举左子树
        for (const right of build(i + 1, hi)) // 枚举右子树
          result.push(new TreeNode(i, left, right))
    }
    return result
  }
  return build(1, n)
}

py

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
        def build(lo: int, hi: int) -> list:
            if lo > hi: return [None]
            result = []
            for i in range(lo, hi + 1):
                for left in build(lo, i - 1):    # 枚举左子树
                    for right in build(i + 1, hi):  # 枚举右子树
                        root = TreeNode(i, left, right)
                        result.append(root)
            return result
        return build(1, n)

• 时间复杂度：$O(\frac{4^n}{\sqrt{n}})$，即卡特兰数 $C_n$，每棵树还需 $O(n)$ 时间构建节点
• 空间复杂度：$O(\frac{4^n}{\sqrt{n}})$，存储所有生成的树

算法思路：

• 对于 BST，任意选择一个节点 i 作为根，则 [lo, i-1] 构成左子树，[i+1, hi] 构成右子树
• 递归函数 build(lo, hi) 返回 [lo, hi] 范围内所有可能的 BST 根节点列表
• 枚举每个 i 作为根，组合所有左子树和右子树的可能性，拼接成完整的树
• 当 lo > hi 时，返回 [null] 表示空子树